package leetcode.hot100;

public class Solution96 {

    public static void main(String[] args) {
        System.out.println(new Solution96().numTrees(19));
    }

    public int numTrees(int n) {
        int[] record = new int[n+1];
        record[0] = 1;
        record[1] = 1;
        for (int i = 2; i <= n; i++) {
            //累加
            for (int j = 0; j <= i-1 ; j++) {
                record[i] += record[j]*record[i-1-j];
            }
        }
        return record[n];
    }


    public int combination(int N, int M){
        long comb = 1, n = N-M+1, m = 1; //C(N-M+1,0)
        while(m<=M){
            comb = comb*n/m;
            n++;
            m++;
        }
        return (int)comb;
    }
}
